package leetcode.code0952;

import java.util.ArrayList;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution2 implements IDebug {

	static Integer[] prime;
	static List<Integer> list;
	static {
		list = new ArrayList<>();
		list.add(2);
		for (int i = 3; i <= 100000 / 2; i += 2) {
			if (isPrime(i)) {
				list.add(i);
			}
		}
		prime = list.toArray(new Integer[list.size()]);
	}

	public static boolean isPrime(int num) {
		for (int i = 3; i * i <= num; i += 2) {
			if (num % i == 0 || i * i == num) {
				return false;
			}
		}
		return true;
	}

	public int largestComponentSize(int[] nums) {
		UnionFind(100000);
		int ans = Integer.MIN_VALUE;
		for (int i = 0; i < nums.length; i++) {
			int num = nums[i];
			if (list.contains(num)) {
				ans = Math.max(ans, this.add(this.findRoot(num)));
				continue;
			}
			int last = 1;
			for (int j = 0; j < prime.length; j++) {
				if (num < prime[j]) {
					break;
				}
				if ((num % prime[j]) == 0) {
					int id = this.findRoot(prime[j]);
					if (last != 1) {
						last = this.union(last, id);
					} else {
						last = id;
					}
				}
			}
			if (last != 1) {
				ans = Math.max(ans, this.add(last));
			}
		}
		return ans;
	}

	int[] roots;
	int[] sizes;
	int[] nums;
	int[] stack;

	public void UnionFind(int n) {
		roots = new int[n];
		sizes = new int[n];
		nums = new int[n];
		for (int i = 0; i < n; i++) {
			roots[i] = i;
			sizes[i] = 1;
		}
		stack = new int[n];
	}

	public int add(int id) {
		nums[id] += 1;
		return nums[id];
	}

	public int findRoot(int id) {
		int root = 0;
		int p = 0;
		while ((root = roots[id]) != id) {
			stack[p++] = id;
			id = root;
		}
		while (p > 0) {
			roots[stack[--p]] = root;
		}
		return root;
	}

	public boolean isSameSet(int id1, int id2) {
		return findRoot(id1) == findRoot(id2);
	}

	public int union(int id1, int id2) {
		int p1 = this.findRoot(id1);
		int p2 = this.findRoot(id2);
		int ans = p1;
		if (p1 != p2) {
			int size1 = this.sizes[p1];
			int size2 = this.sizes[p2];
			if (size1 < size2) {
				this.roots[p1] = p2;
				this.sizes[p2] = size1 + size2;
				this.sizes[p1] = 0;
				this.nums[p2] += this.nums[p1];
				this.nums[p1] = 0;
				ans = p2;
			} else {
				this.roots[p2] = p1;
				this.sizes[p1] = size1 + size2;
				this.sizes[p2] = 0;
				this.nums[p1] += this.nums[p2];
				this.nums[p2] = 0;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(84, this.largestComponentSize(H.str2array3(
				"[2,7,522,526,535,26,944,35,519,45,48,567,266,68,74,591,81,86,602,93,610,621,111,114,629,641,131,651,142,659,669,161,674,163,180,187,190,194,195,206,207,218,737,229,240,757,770,260,778,270,272,785,274,290,291,292,296,810,816,314,829,833,841,349,880,369,147,897,387,390,905,405,406,407,414,416,417,425,938,429,432,926,959,960,449,963,966,929,457,463,981,985,79,487,1000,494,508]")));
		H.compare(6, this.largestComponentSize(H.str2array3("[1,2,3,4,5,6,7,8,9]")));
		H.compare(4, this.largestComponentSize(H.str2array3("[4,6,15,35]")));
		H.compare(2, this.largestComponentSize(H.str2array3("[20,50,9,63]")));
		H.compare(8, this.largestComponentSize(H.str2array3("[2,3,6,7,4,12,21,39]")));
		H.compare(12, this
				.largestComponentSize(H.str2array3("[425,938,429,432,926,959,960,449,963,966,929,457,463,981,985]")));
		H.compare(19, this.largestComponentSize(H.str2array3(
				"[81265,25601,52183,66947,60257,93927,27309,27959,8443,91457,67915,53068,48883,39727,27814,69767,58391,66107,35933,72407,98037,74323,74201,33997,97349,16843,46071,39453,27581,14799,87833,8452,76511,16792,55253,27819,87121,85879,57283,54199,40364,77171,81869,77541,26961,80944,98801,55339,523,38447,14839,53693,65119,89099,7451,91449,73973,6689,4267,94538,91033,56773,38711,5139,62276,7927,77527,82025,63601,60521,89521,88256,55889,67399,44617,1199,59433,44209,12387,61031,22234,7061,26206,94441,88052,59063,34636,81799,55294,96149,75239,"
						+ "63524,48963,68909,49463,46519,84746,41603,13789,31498]")));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
//		System.out.println(175 % 3);
//		System.out.println(5 % 150);
	}

}
